
public class p1007_1266ms {

	public static//
	// -----
	// -----
	class Main {
		public static void main(String[] args) throws Exception {
			java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
			String[] parts = reader.readLine().split(" ");
			int m = Integer.parseInt(parts[1]);
			Object[][] list = new Object[m][];
			for (int i = 0; i < m; i++) {
				String line = reader.readLine();
				list[i] = new Object[] { count(line), line };
			}
			mergeSort(list, 0, m);
			for (Object[] entry : list)
				System.out.println((String) entry[1]);
		}

		static int count(String line) {
			int a = 0, c = 0, g = 0, sum = 0;
			for (int i = line.length() - 1; i >= 0; i--) {
				char x = line.charAt(i);
				if (x == 'A') {
					a++;
				} else if (x == 'C') {
					c++;
					sum += a;
				} else if (x == 'G') {
					g++;
					sum += a + c;
				} else {
					sum += a + c + g;
				}
			}
			return sum;
		}

		static void mergeSort(Object[][] list, int start, int end) {
			if (end - start <= 1)
				return;
			int mid = (start + end) / 2;
			if (mid - start > 1)
				mergeSort(list, start, mid);
			if (end - mid > 1)
				mergeSort(list, mid, end);
			merge(list, start, mid, end);
		}

		static void merge(Object[][] list, int start, int mid, int end) {
			int i1max = mid - start;
			Object[][] tmp = new Object[i1max][];
			System.arraycopy(list, start, tmp, 0, i1max);
			int i = start, i1 = 0, i2 = mid;
			while (true) {
				if (i1 == i1max)
					return;
				if (i2 == end) {
					System.arraycopy(tmp, i1, list, i, i1max - i1);
					return;
				}
				int v1 = (Integer) tmp[i1][0];
				int v2 = (Integer) list[i2][0];
				if (v1 <= v2) {
					list[i++] = tmp[i1++];
				} else {
					list[i++] = list[i2++];
				}
			}
		}
	}

	// -----
	// -----

	public static void main(String[] args) throws Exception {
		Judge.run();
	}

}
